home *** CD-ROM | disk | FTP | other *** search
/ The Programmer Disk / The Programmer Disk (Microforum).iso / xpro / c / pro12 / testsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-03-31  |  5.0 KB  |  212 lines
  1. /***********************************************************************/
  2. /*  TESTSORT: Sort Tester/Analyzer program                             */
  3. /*  See the function declaration for calling information.              */
  4. /*  Program is by Bruce Feist; please contact me at any of the below   */
  5. /*  if you have any questions, problems, or comments.                  */
  6. /*  CompuServe: 71320,3635; use Easyplex, BPROGB, or MACDEV            */
  7. /*  Enlightened Bulletin Board: (703) 370-9528, N/8/1                  */
  8. /*                                                                     */
  9. /* Feel free to make use of this code in your own programs.            */
  10. /***********************************************************************/
  11.  
  12. #define FALSE 0
  13. #define TRUE 1
  14. #define VERBOSE FALSE
  15.  
  16. #include <stdio.h>
  17. #include <process.h>
  18. #include <alloc.h>
  19. #include <stdlib.h>
  20. #include <mem.h>
  21. #include <string.h>
  22. #include <conio.h>
  23. #include <ctype.h>
  24. #include <math.h>
  25. #include <time.h>
  26. #include <stdlib.h>
  27.  
  28. #include "sort.h"
  29.  
  30. typedef int cmpfunc(const void *, const void *);
  31.  
  32. cmpfunc comp;
  33. void more (void);
  34. void show_array (double *, int);
  35. static int qusort (void *, int, int, int());
  36. double drand (void);
  37.  
  38.  
  39. void
  40. main()
  41. {
  42.   double *list, bias;
  43.   int n_entries, entry_number, display;
  44.   long  start_time, stop_time;
  45.   char sort_type;
  46.   int (*sort)(void *base, size_t nelem, size_t width, cmpfunc comp);
  47.  
  48.   while (TRUE)
  49.   {
  50.     printf ("Enter the number of entries to be sorted: ");
  51.     fflush (stdout);
  52.     scanf ("%d", &n_entries);
  53.     if (n_entries <= 0)
  54.       exit(0);
  55.     list = malloc (n_entries * sizeof (double));
  56.     if (list != NULL)
  57.       break;
  58.     printf ("Insufficient memory.  Please choose a smaller size.\n");
  59.     }
  60.  
  61.   do
  62.   {
  63.     puts ("Biases can range from -1 to 1; they do not have to be integers.");
  64.     puts ("-1 is reverse sorted, 0 is random, and 1 is sorted.");
  65.     printf ("Your desired bias is:  ");
  66.     scanf ("%lf", &bias);
  67.     } while (bias < -1 || bias > 1);
  68.  
  69.   printf ("Display the list generated?  (y or n):  ");
  70.   while (TRUE)
  71.   {
  72.     display = toupper (getch());
  73.     if (display == 'Q')
  74.     {
  75.       puts ("Quit");
  76.       exit (0);
  77.       }
  78.     if (display == 'Y' || display == 'N')
  79.       break;
  80.     printf ("\aEnter y or n:  ");
  81.     }
  82.   display = (display == 'Y');
  83.   puts (display ? "Yes" : "No");
  84.  
  85.   printf ("I)nsertion, S)hell's, M)erge, merge L)ist, Q)uick, or H)eapsort?  ");
  86.   do
  87.   {
  88.     sort_type = toupper (getch ());
  89.     switch (sort_type)
  90.     {
  91. #pragma warn -sus
  92.       case 'I': sort = isort;
  93.         puts ("Insertion");
  94.         break;
  95.       case 'M': sort = msort;
  96.         puts ("Merge");
  97.         break;
  98.       case 'Q': sort = qusort;
  99.         puts ("Quick");
  100.         break;
  101.       case 'H': sort = hsort;
  102.         puts ("Heap");
  103.         break;
  104.       case 'S': sort = ssort;
  105.         puts ("Shell's");
  106.         break;
  107.       case 'L': sort = mlsort;
  108.         puts ("Merge List");
  109.         break;
  110. #pragma warn .sus
  111.       default:
  112.         sort = NULL;
  113.         putchar ('\a');
  114.         break;
  115.       } /* end switch */
  116.     } while (sort == NULL);
  117.  
  118.   printf ("\nInitializing list");
  119.  
  120.   for (entry_number = 0;
  121.        entry_number < n_entries;
  122.        entry_number++)
  123.   {
  124.     if ((entry_number * 60 / n_entries) > ((entry_number-1) * 60 / n_entries))
  125.       printf (".");
  126.     list[entry_number] = entry_number * bias + drand();
  127.     } /* end for */
  128.  
  129.   printf ("\n");
  130.   if (display)
  131.     show_array (list, n_entries);
  132.  
  133. #if FALSE
  134.   more();
  135. #endif
  136.  
  137.   puts ("Sorting. . .");
  138.   time (&start_time);
  139.   if ((*sort) (list, n_entries, sizeof (list[0]), comp) != S_OK)
  140.   {
  141.     puts ("Unable to perform sort.");
  142.     }
  143.  
  144.   time (&stop_time);
  145.  
  146.   puts ("Done sorting.");
  147.   if (display)
  148.     show_array (list, n_entries);
  149.  
  150.   printf ("Verifying sort");
  151.   for (entry_number = 1;
  152.        entry_number < n_entries;
  153.        entry_number++)
  154.   {
  155.     if ((entry_number * 60 / n_entries) > ((entry_number-1) * 60 / n_entries))
  156.       printf (".");
  157.     if (comp(list + entry_number - 1, list + entry_number) > 0 &&
  158.     comp(list + entry_number, list + entry_number - 1) < 0)
  159.       printf ("\nSort error: # %d (%lf) > # %d (%lf).\n",
  160.           entry_number - 1, list[entry_number-1],
  161.           entry_number, list[entry_number]);
  162.     } /* end verification loop */
  163.   printf ("\n");
  164.  
  165.   printf ("Time elapsed: %ld seconds.\n", stop_time - start_time);
  166.  
  167.   exit (0);
  168.   }
  169.  
  170.  
  171. int
  172. comp (const void *i, const void *j)
  173. {
  174.   register int retcode;
  175.  
  176.   retcode = (*(double *) i < *(double *)j) ? -1 : 1;
  177. #if VERBOSE
  178.   printf ("comp (%p: 1.4lf, %p: %1.4lf) = %d.\n", i, *(double *) i,
  179.     j, *(double *) j, retcode);
  180. #endif
  181.   return retcode;
  182.   }
  183.  
  184.  
  185. void
  186. show_array (double *list, int n_entries)
  187. {
  188.   int entry;
  189.  
  190.   for (entry = 0;
  191.        entry < n_entries;
  192.        entry++)
  193.     printf ("%lf ", list [entry]);
  194.   printf ("\n");
  195.   }
  196.  
  197.  
  198. double
  199. drand (void)
  200. {  /* Returns a random number from 0 to 1. */
  201.  
  202.   return (random (1000) / 1000.0);
  203.  
  204.   } /* end drand */
  205.  
  206.  
  207. int
  208. qusort (void *base, int nelem, int width, int compare())
  209. {
  210.   qsort (base, nelem, width, compare);
  211.   return S_OK;
  212.   }  /* end qusort */